package recursive;

import beans.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author pengfei.hpf
 * @date 2020/3/7
 * @verdion 1.0.0
 * 满二叉树是一类二叉树，其中每个结点恰好有 0 或 2 个子结点。
 *
 * 返回包含 N 个结点的所有可能满二叉树的列表。 答案的每个元素都是一个可能树的根结点。
 *
 * 答案中每个树的每个结点都必须有 node.val=0。
 *
 * 你可以按任何顺序返回树的最终列表。
 *
 *  
 *
 * 示例：
 *
 * 输入：7
 * 输出：[[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]
 * 解释：
 *
 *  
 *
 * 提示：
 *
 * 1 <= N <= 20
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/all-possible-full-binary-trees
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class AllPossibleFBT {
    public List<TreeNode> allPossibleFBT(int N){
        if(N == 0 || N %2 == 0){
            List<TreeNode> list = new ArrayList<TreeNode>();
            return list;
        }
        List<TreeNode> list = new ArrayList<TreeNode>();
        if(N == 1){
            TreeNode node = new TreeNode(0);
            list.add(node);
            return list;
        }
        N = N -1;
        for(int i = 1; i <= N/2; i ++){
            if(i %2 == 0){
                continue;
            }
            List<TreeNode> left = allPossibleFBT(i);
            List<TreeNode> right = allPossibleFBT(N - i);

            list.addAll(buildTree(left, right));
            if(i != N - i){
                list.addAll(buildTree(right, left));
            }

        }
        return list;
    }

    private List<TreeNode> buildTree(List<TreeNode> left, List<TreeNode> right){
        List<TreeNode> res = new ArrayList<>();
        for(TreeNode l: left){
            for(TreeNode r: right){
                TreeNode node = new TreeNode(0);
                node.left = l;
                node.right = r;
                res.add(node);
            }
        }
        return res;
    }
}
